package com.lzp.leetcode

/**
 * https://leetcode-cn.com/problems/longest-palindromic-substring/
 * @describe: 最长回文子串
 * @Author: lixiaopeng
 * @Date: 4/21/21
 * 回文子串 正序和反序是一样的字符串
 * 例如：
 * 上海自来水来自海上
 *
 * 大名小磨香油油香磨小名大
 */


fun main() {
    println("${solution5("1abbccbba")}")
    //println("${solution5("12abccba1")}")

    /*println("${solution5("12abbcbba34")}")
    println("${solution5("12abccba34")}")

    println("${solution5("12abbcbba")}")
    println("${solution5("12abccba")}")

    println("${solution5("abbcbba34")}")
    println("${solution5("abccba45")}")*/
}

/**
 * 解法2：
 * 因为是回文，所以把文字反转后，仍然是回文，因此问题就变成了反转后，找最长公共子串的问题
 *
 * 最长公共子串，可以参考[Leetcode1143]
 */
fun solution55(input: String): String{

    return ""
}

/**
 * 解题思路
 * 1.回文串分两种
 *      中心数字为奇数个数：aba
 *      中心数字为偶数个数：abba
 * 2.任何一个回文字符串，将中心当成一个整体，仍然是回文字符串。
 *      例如：abcdcba 以d为中心，两边分别扩展N个字符看成一个整体后，仍然是回文串 ab(cdc)ba，讲（）内的文字看成一个整体，仍然是回文串
 * 3.相同的字符在一起，必然是回文串
 *
 *
 */
fun solution5(input: String): String {
    if (input.isEmpty()) {
        return ""
    }
    if (input.length == 1) {
        return input
    }

    var start = 0
    var end = 0

    for (i in input.indices) {
        //中心为奇数个 aba类型的
        val len1 = expandAroundCenter(input, i, i)
        //中心为偶数个 abba类型的
        val len2 = expandAroundCenter(input, i, i + 1)
        val len = Math.max(len1, len2)
        if (len > end - start) {
            start = i - (len - 1) / 2
            end = i + len / 2
        }
        println( "当 i = $i 时找到回文 = ${input.substring(start, end + 1)}   $start  $end")
    }
    return input.substring(start, end + 1)
}

/**
 * 找回文串的长度
 */
private fun expandAroundCenter(s: String, left: Int, right: Int): Int {

    var l = left
    var r = right
    //左侧指针，和右侧指针不可越界
    //当左侧等于右侧时，进行扩散
    while (l >= 0 && r < s.length && s[l] == s[r]) {
        l--
        r++
    }
    return r - l - 1
}